β

Как стать автором
Курсы по фронтенду
Какой вы ML-специалист: составим портреты типичных ML’щиков

Моя лентаВсе потоки

wikendp 17 фев 2023 в 22:16

Hashmap(map) по версии Golang. Часть 2

Средний

11 мин

11K

Программирование*Алгоритмы*Go*

FAQ

github.com/w1kend/gophers

Всем привет. Продолжаем реализовывать hashmap из исходников Go 1.19. Во второй части рассмотрим generic ключи и рост мапы. Узнаем что такое нерефлексивные ключи, как происходит итерация во время роста и немного про коробочное хеширование.

Часть 1

Некоторые определения из прошлой части:

бакет - структура данных в которой хранятся ключи, значения и топхеш;

рост - при достижении определенного порога значений в бакете (в среднем) начинается рост чтобы поддерживать константную скорость операций с мапой. Выделяется память под х2 бакетов;

эвакуация - в процессе роста старые бакеты "эвакуируются" в новое место.

Generic ключи

Хэшируем все что движется comparable:

Из коробки Go не предоставляет доступ к функциям хеширования, которые используются в map. Однако есть продвижения в этом направлении - в go 1.19 в пакете maphash были добавлены функции Bytes и String для хеширования массива байт и строки соответственно. Но для использования generic ключей в нашей map'е этого недостаточно. Будем пользоваться магией, про которую можно почитать здесь.

dolthub/maphash или как добраться до функции хеширования из runtime

Компилятор Go генерирует функцию хеширования для каждого типа ключа, который мы используем в нашем коде. Найти ее можно в следующей структуре maptype:

runtime/type.go

type maptype struct {
/* ... */
// function for hashing keys (ptr to key, seed) -> hash
hasher func(unsafe.Pointer, uintptr) uintptr
/* ... */
}

Добраться до нее можно с помощью приведения типов и пакета unsafe:

dolthub/maphash/runtime.go

func getRuntimeHasher[K comparable]() (h hashfn, seed uintptr) {
a := any(make(map[K]struct{})) // создаем мапу с нужным типом ключа
i := (*mapiface)(unsafe.Pointer(&a)) // приводим к нашей структуре, которая идентична тому что под капотом
h, seed = i.typ.hasher, uintptr(i.val.hash0) // забираем работу компилятора
return
}

type mapiface struct {
typ *maptype
val *hmap
}

// go/src/runtime/type.go
type maptype struct {
/* ... */
hasher func(unsafe.Pointer, uintptr) uintptr // заветная функция хеширования
/* ... */
}

// go/src/runtime/map.go
type hmap struct {
/* ... */
}

Получаем следующую функцию для хеширования  для comparable типов:

func (h Hasher[K]) Hash(key K) uint64 // K - comparable

Зачем использовать магию?

Хеширование под капотом по возможности использует AES инструкции процессора. Это будет работать быстрее (в теории) в отличии от кода на чистом Go.

Добавляем себе. Теперь создание мапы выглядит так:

type hmap[K comparable, V any] struct {
/* ... */
hasher maphash.Hasher[K]
/* ... */
}

func New[K comparable, V any](size int) Hashmap[K, V] {
h := new(hmap[K, V])

B := uint8(0)
for overLoadFactor(size, B) {
B++
}
h.B = B

h.buckets = make([]bucket[K, V], bucketsNum(h.B))

/* новый код */
h.hasher = maphash.NewHasher[K]() // новый хэшер для comparable типов

return h
}

// использование
func (h *hmap[K, V]) locateBucket(key K) (tophash uint8, targetBucket uint64) {
hash := h.hasher.Hash(key)
/* ... */
}

Про нерефлексивные ключи

Такими называются ключи которые неравны сами себе - x != x. Их в Go есть.

Мы можем использовать NaN как ключ в мапе с некоторыи оговорками:

каждый раз при добавлении элемента с таким ключом будет создаваться новый элемент;

добраться до значения по такому ключу можно только при итерации;

нельзя удалить;

хэш от такого ключа всегда разный, по-этому элементы будут разбросаны по разным бакетам.

m := make(map[float64]int)
for i := 0; i < 4; i++ {
m[math.NaN()] = i
}
fmt.Println(m) // map[NaN:1 NaN:0 NaN:3 NaN:2]
fmt.Println(m[math.NaN()]) // 0

Эвакуация

Рост мапы начинается в двух случаях:

бакеты в среднем заполнены на больше чем ~80%. В таком случае количество бакетов увеличивается вдвое;

и частный случай (не закодирован) - количество overflow бакетов примерно равно количеству самих бакетов.

Каким образом получить частный случай

В процессе использования мапы у нас есть N бакетов и каждый из них (по отдельности, иначе сработал бы тригер на обычный рост) переполнялся и несколько элементов приходилось сохранять в overflow бакетах. Далее удалялись те элементы, которые находились в основных бакетах. Заполнив так несколько бакетов получим ситуацию когда сами бакеты полупустые, а большинство данных лежит в overflow.

Проблема в таком случае в том что каждый раз при поиске/вставке/удалении нужно итерироваться сначала по основному бакету, а потом по overflow.

В отличии, например, от Python и Java в Go рост мапы происходит постепенно. Каждый раз перед добавлением или удалением элемента переносятся данные из 1-2 бакетов.

Для роста нам потребуется несколько новых полей:

type hmap[K comparable, V any] struct {
len int // количество реальных значений в мапе
B uint8 // log_2 от количества бакетов
buckets []bucket[K, V] // слайс бакетов
hasher maphash.Hasher[K] // функция хэширования из рантайма

/* новые поля */
oldbuckets *[]bucket[K, V] // слайс старых бакетов
numEvacuated uint64 // счетчик прогресса роста. все бакеты меньше этого значения эвакуированы
}

Подготовка в росту:

// выделяем память под новые бакеты, увеличиваем счетчик количества бакетов
func (m *hmap[K, V]) startGrowth() {
oldBuckets := m.buckets
m.B++ // растем только на увеличение
m.buckets = make([]bucket[K, V], bucketsNum(m.B))
m.oldbuckets = &oldBuckets
m.numEvacuated = 0
}

Так выглядит эвакуация и триггер роста в методе Put:

func (h *hmap[K, V]) Put(key K, value V) {
tophash, targetBucket := h.locateBucket(key)

// проверяем "триггер" роста если кол-во элементов в бакете увеличится
if !h.isGrowing() && overLoadFactor(h.len+1, h.B) {
h.startGrowth()
}

// сначала эвакуируем нужный бакет
if h.isGrowing() {
h.growWork(targetBucket)
}

if h.buckets[targetBucket].Put(key, tophash, value) {
h.len++
}
}

Также во время роста проверяем эвакуировался ли бакет перед поиском значения оттуда:

func (h *hmap[K, V]) Get2(key K) (V, bool) {
tophash, targetBucket := h.locateBucket(key)

b := &h.buckets[targetBucket]

if h.isGrowing() {
oldB := &(*h.oldbuckets)[targetBucket&h.oldBucketMask()] // берем старый бакет
if !oldB.isEvacuated() { // если он еще не эвакуировался, то ищем значение в нем
b = oldB
}
}

return b.Get(key, tophash)
}

Собственно эвакуация

Сам алгоритм несложный (практически) - проходим по все элементам в бакете, выбираем новый бакет и переносим ключ, значение и топхеш.

Куда переезжать

При росте мапы количество бакетов увеличивается вдвое. Если разделить слайс новых бакетов на две половины, то для каждого элемента внутри старого бакета есть два пути this is the way - либо в первую половину либо во вторую. А если считать каждую половину новых бакетов отдельным слайсом, то можно сказать что в пределах такой половины индекс бакета для элемента не поменяется.
Пример

Было 8 бакетов, мы начали рост, количество бакетов удвоилось и стало 16. В таком случае каждый элемент бакета по индексу 3(четвертый бакет) перенесется либо в бакет в первой половине по индексу 3, либо во второй по индексу 11 (3+8). Соответственно последний бакет с индексом 7 переносится либо в 7ой либо в 15й(7+8).

Бакеты из разных половин храним во вспомогательной структуре. Там же держим индекс следующего свободного места.

// evacDst вспомогательная структура для эвакуации бакета
type evacDst[K comparable, V any] struct {
b *bucket[K, V] // ссылка но новый бакет
i uint // индекс следующего свободного места в бакете
}

// храним ссылки на два новых бакета, в которые будут переноситься данные из текущего
halfs := [2]evacDst[K, V]{
{b: &m.buckets[oldbucket]}, // oldBucket равен номеру старого бакета, который хотим эвакуировать
{b: &m.buckets[oldbucket+newBit]}, // newBit равен кол-ву старых бакетов
}

Выбирается половина с помощью хеша от ключа и нового бита маски. При росте к новой маске добавляется бит, который и решает изменится ли результат операции hash&mask или нет.

newBit := m.numOldBuckets()
hash := m.hasher.Hash(*key)
var useSecond uint8
if hash&newBit != 0 {
useSecond = 1
}
Почему newBit

newBit - старое количество бакетов. В двоичном представлении это один не нулевой бит, которым новая маска отличается от старой.
При росте с 8 до 16 бакетов
newBit == 8 (1000)
mask == 15 (1111)
oldMask == 7 (0111)
От сюда и название переменной.

Полный цикл эвакуации:

newBit := m.numOldBuckets()
/* ... */
for ; b != nil; b = b.overflow {
// итерируемся по старому бакету
for i := 0; i < bucketSize; i++ {
top := b.tophash[i]

// используем флаги tophash для проверки пустых ячеек
if isCellEmpty(top) {
b.tophash[i] = evacuatedEmpty
continue
}

key := &b.keys[i]
value := &b.values[i]

// опять берем хэш от ключа
hash := m.hasher.Hash(*key)

// флаг использования второй половины новых бакетов
var useSecond uint8

// проверяем зависит ли местоположение элемента от нового бита
if hash&newBit != 0 {
useSecond = 1
}

// evacuatedFirst, evacuatedSecond - константные флаги для массива tophash показывающие в какую половину переехал элемент
// evacuatedFirst + useSecond == evaluatedSecond
b.tophash[i] = evacuatedFirst + useSecond

//выбираем нужный бакет
dst := &halfs[useSecond]
// проверяем кол-во элементов
if dst.i == bucketSize {
dst.b = newOverflow(dst.b) // если нужно создаем overflow
dst.i = 0
}
// добавляем элемент по конкретному индексу
dst.b.putAt(*key, top, *value, dst.i)
dst.i++
}
}

В оригинальном алгоритме есть такая проверка:

if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}

Она случается при переносе каждого элемента. На мой взгляд это странно, так как константы нельзя переопределять, и хватило бы одной проверки во время компиляции. Я заменил это на такую проверку:

func _() {
var x [1]struct{}
_ = x[evacuatedFirst-2]
_ = x[evacuatedSecond-3]
}

Итерация

Плюсы такого алгоритма роста - нет просадок производительности при эвакуации большого количества данных, как если бы мы это делали одним подходом. Из минусов - нужно это учитывать при вставке/удалении/поиске значений, а особенно при итерации.

Для этого существует отдельная структура, которая хранит ссылки на ключ и значение, и состояние итерации:

type hiter[K comparable, V any] struct {
key *K // ключ
elem *V // значение
m *hmap[K, V] // сама мапа
buckets *[]bucket[K, V] // массив бакетов по которым итерируемся
currBktPtr *bucket[K, V] // текущий бакет
startBucket uint64 // рандомно выбранный начальный бакет
offset uint8 // рандомный оффсет, с которого начинается итерация внутри бакета
wrapped bool // сделали круг по массиву бакетов
B uint8 // log_2 от кол-ва бакетов на момент старта итерации
i uint8 // позиция следующего элемента в текущем бакете
currBucketNum uint64 // номер текущего бакета
checkBucket uint64 // номер бакета для дополнительной проверки. todo из-за эвакуации иногда приходится смотреть данные сразу в двух бакетах
}

Инициализируем. Здесь же происходит магия "рандомной" последовательности элементов при каждой новой итерации: выбирается случайный бакет, с которого начнется итерация, и отступ, с которого будут возвращаться элементы внутри каждого бакета.

func iterInit[K comparable, V any](m *hmap[K, V]) *hiter[K, V] {
h := hiter[K, V]{}

if m == nil || m.len == 0 {
return &h
}

h.m = m
h.B = m.B
h.buckets = &m.buckets
// выбираем рандомный бакет
h.startBucket = rand.Uint64() & bucketMask(m.B)
// выбираем позицию, с которой начинается итерация внутри бакета
h.offset = uint8(uint8(h.startBucket) >> h.B & (bucketSize - 1))
h.currBucketNum = h.startBucket

// сразу выполняем одну итерацию
h.next()

return &h
}

Алгоритм итерации можно разделить на две части:

простой случай - когда мапа не в процессе роста;

сложный - в процессе роста. Для этого потребуются дополнительные проверки.

В первом случае можно просто итерироваться по бакетам. Заносим в локальные переменные состояние итерации и выбираем бакет:

b := it.currBktPtr
bucketNum := it.currBucketNum
i := it.i
checkBucket := it.checkBucket
next:
// выбираем следующий бакет
if b == nil {
if bucketNum == it.startBucket && it.wrapped {
// конец итерации
it.key = nil
it.elem = nil
return
}
checkBucket = noCheck //
b = &it.m.buckets[bucketNum] // бакет внутри которого будет искать данные

bucketNum++ // номер след. бакета
if bucketNum == bucketsNum(it.B) {
// если "замкнули круг" то проставляем соответствующий флаг
bucketNum = 0
it.wrapped = true
}
i = 0
}

Итерируемся:

// bucketSize - константа количества элементов внутри бакета
for ; i < bucketSize; i++ {
// определяем элемент, который будем переносить, в соответствии с оффсетом
offI := (i + it.offset) & (bucketSize - 1)
top := b.tophash[offI]
// если ячейка пустая
if isCellEmpty(top) || top == evacuatedEmpty {
continue
}
key := &b.keys[offI]
elem := &b.values[offI]

// проставляем значения в структуру итерации
it.key = key
it.elem = elem
// обновляем текущий стейт
it.currBucketNum = bucketNum
if it.currBktPtr != b {
it.currBktPtr = b
}
it.i = i + 1
return
}
// идем в overflow
b = b.overflow
i = 0
goto next // к выбору следующего бакета

Для того чтобы итерироваться в процессе роста мапы добавим некоторые изменения в алгоритм. При выборе следующего бакета x будем учитывать что данные из старого бакета oldX возможно еще не эвакуировались, и нужно начать итерацию по oldX.

Так как вариантов переноса элементов из бакета только два, то при проходе по старону (не эвакуированному) oldX бакету, будем возвращать только те элементы, которые перейдут в бакет x.

Изменения в месте выбора следующего бакета:

// если рост еще не завершен, то старые бакеты тоже нужно учитывать
if it.m.isGrowing() && it.B == it.m.B {
// runtime/map.go:890
// итерацию начали во время роста. проверяем старый бакет
// если он еще не эвакуировался, то проходим по нему, и возвращаем только те элементы
// которые мигрируются в текущий бакет
oldBucketNum := bucketNum & it.m.oldBucketMask()
b = &(*it.m.oldbuckets)[oldBucketNum]
if !b.isEvacuated() {
checkBucket = bucketNum
} else {
// иначе просто итерируемся по bucketNum
checkBucket = noCheck
b = &it.m.buckets[bucketNum]
}
} else {
checkBucket = noCheck
b = &it.m.buckets[bucketNum]
}
bucketNum++
if bucketNum == bucketsNum(it.B) {
// если "замкнули круг" то проставляем соответствующий флаг
bucketNum = 0
it.wrapped = true
}
i = 0

Учитываем, что если мы в старом бакете, то проверяем нужно ли вернуть элемент.

Здесь же учитывается случай, когда key != key (NaN). Так как хеш от NaN будет каждый раз новый, то нам нужен способ "рандомного" переноса. К тому же нужно уметь воспроизводить такой выбор. По-этому для таких значений вместо хеша ключа используется tophash, а именно его последний бит, определяющий в какую половину перенесется значение.

if checkBucket != noCheck && !it.m.sameSizeGrow() {
// runtime/map.go:925
// случай когда мы начали итерацию во время роста и он еще не закончился
// oldbucket слайс еще не эвакуировался. или, как минимум, он не был эвакуирован
// когда мы начали итерацию.
// по-этому пропускаем ключи которые попадут в навый бакет на другой позиции
// (при эвакуации каждый элемент бакета либо остается в бакете по старому индексу либо по новому)
if key == key {
hash := it.m.hasher.Hash(*key)
if hash&bucketMask(it.B) != checkBucket {
continue
}
} else {
// runtime/map.go:941
// если ключ не равен себе(NaN) мы выбираем "рандомное" место переноса
if checkBucket>>(it.B-1) != uint64(b.tophash[offI]&1) {
continue
}
}
}

И в последнее отличие в алгоритме - нам нужно проверить что элемент итерации не переехал в другой бакет, то есть его tophash не равен одной из констант. В случае если элемент все таки эвакуировался, то придется воспользоваться обычным поиском через функцию Get().

if (top != evacuatedFirst && top != evacuatedSecond) || key != key {
// нашли элементы на текущем шаге итерации
it.key = key
it.elem = elem
} else {
// мапа выросла с момента итерации
// нужные данные для текущего ключа где-то в другом месте
// этот кейс для случай когда ключ был удален/обновлен или удален и добавлен еще раз.

re, ok := it.m.Get2(*key)
if !ok {
continue // ключ был удален
}
it.key = key
it.elem = &re
}

Консистентность данных во время итерации нам гарантирует следущая проверка в функции next(). Она спасает от конкурентного обращения к мапе во время итерации, что привело бы к дополнительной эвакуации нескольких бакетов.

if it.m.flags&hashWriting != 0 {
panic("concurrent map iteration and map write")
}

Запустим бенчмарк из прошлой части, который просто добавляет N элементов в мапу с начальным размером 1000. Стал похож на то, что есть под капотом:

go test . -run=^$ -bench ^BenchmarkPutWithOverflow$ -benchmem
goos: darwin
goarch: arm64
pkg: github.com/w1kend/go-map
BenchmarkPutWithOverflow/gen-map__(string_key)10000-8 37374638 29.77 ns/op 0 B/op 0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)10000-8 41619038 27.21 ns/op 0 B/op 0 allocs/op
BenchmarkPutWithOverflow/gen-map__(string_key)100000-8 29636793 34.50 ns/op 0 B/op 0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)100000-8 30507568 34.89 ns/op 0 B/op 0 allocs/op
BenchmarkPutWithOverflow/gen-map__(string_key)1000000-8 14918946 79.41 ns/op 0 B/op 0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)1000000-8 19115414 63.17 ns/op 0 B/op 0 allocs/op
BenchmarkPutWithOverflow/gen-map__(string_key)10000000-8 6472369 267.0 ns/op 212 B/op 0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)10000000-8 6640574 248.4 ns/op 211 B/op 0 allocs/op

Исходники для поиграться здесь. Зачем? Например, при использовании арены из Go 1.20 для хранения бакетов производительность по бенчмарку практически не изменилась (стало лучше при 10кк+ элементов).

На этом все, спасибо за внимание (:

Ссылки

Source code

Картинки гоферов

Hacking Go's Runtime with Generics

Теги:

go

hashmap

структуры данных

Хабы:

Программирование

Алгоритмы

Go

+9

40

2
+2

10

Карма

0

Рейтинг

Sergei Makarov @wikendp

Пользователь

Подписаться

Комментарии 2
+2

Публикации

Лучшие за суткиПохожие

A_Tsymbalyuk 13 часов назад

Физика ошибок не прощает. Она догонит тебя на крыше и заставит платить (дважды)

Простой

6 мин

8.1K

Кейс

+40

35

25
+25

BabayMazay 12 часов назад

Самодельные французские радиолампы 1920 г. Часть 3. Разрядная трубка, лампа накаливания

Средний

9 мин

1.5K

Ретроспектива

+33

9

11
+11

Bright_Translate 8 часов назад

Как я от нечего делать замедлил Postgres в 42 000 раз

Средний

11 мин

2.6K

Кейс

Перевод

+27

19

2
+2

lokosst 12 часов назад

Выделенные серверы + Kubernetes: практическое руководство

17 мин

2.4K

Туториал

+21

23

0

butivskiydm 11 часов назад

Моё мини-исследование про продолжительность жизни в России

Простой

2 мин

6.3K

Мнение

+19

17

59
+59

JetHabr 11 часов назад

«Плохие парни работают просто»: пентестеры разбирают реальные кейсы

Средний

9 мин

2.1K

Кейс

+17

19

1
+1

k0mar0v 14 часов назад

HTC Desire HD: история, дизайн и возможности легендарного смартфона

6 мин

2.6K

+17

5

5
+5

MaFrance351 13 часов назад

Домофон Лидер-М. Как скрестить трубку с ключом и всем проиграть

Простой

4 мин

2.5K

+16

5

6
+6

psygalaxy 13 часов назад

Как мы ускорили проверку документации с помощью AI-агента: от боли к решению

Средний

25 мин

1.8K

Обзор

+16

29

9
+9

kubelet 16 часов назад

DNS-хаос, зомби-поды и майнеры в кластере: самые невероятные случаи при работе с Kubernetes

Простой

14 мин

1.2K

Кейс

+16

23

1
+1

Исследование: как и где ML-специалисты используют ИИ. Расскажите о своем опыте
Опрос

Показать еще

Минуточку внимания

Событие

Как построить IT-бренд через вирусный контент и юмор

Событие

Хабр приглашает маркетологов и пиарщиков на тест-драйв

Турбо

Полный свайп: оцени, подходит ли тебе работа в IT-ритейле

Читают сейчас

Как превратить ноутбук в полноценное рабочее место не хуже стационарного ПК

12K

71
+71

Нашел ЛЯП в игре 5букв от Т-банка, который позволяет со 100% вероятностью угадать скрытое слово

54K

115
+115

Как выйти из IT?.. и пойти слесарем на завод. Моя попыточка дауншифтинга [4\5]

1.4K

11
+11

Моё мини-исследование про продолжительность жизни в России

6.3K

59
+59

GPT-5 получит модуль для борьбы с «галлюцинациями» — The Information

674

3
+3

Исследование: как и где ML-специалисты используют ИИ. Расскажите о своем опыте
Опрос

Истории

История Яндекс Почты

С Днём сисадмина!

Как расти в ИТ: советы, гайды и опыт сеньоров

1 055 450 очков в облаке – попробуй обогнать

Годнота из блогов компаний

Ближайшие события

7 августа

Мем-пати: как построить IT-бренд через вирусный контент и юмор

Москва

Больше событий в календаре

Маркетинг

13 августа

Как повысить эффективность врача в стоматологии на 25% с помощью ИИ?

Онлайн

Больше событий в календаре

Менеджмент

13 августа

Тест-драйв Хабра для маркетологов и пиарщиков

Москва

Больше событий в календаре

Маркетинг

16 августа

«ИТ-летник» — конференция от Совкомбанк Технологий

Казань

Больше событий в календаре

Разработка

Аналитика

3 сентября

«GoCloud Tech 2025» — IT-конференция про облака и AI

Москва • Онлайн

Больше событий в календаре

Разработка

18 – 19 сентября

Конференция по корпоративному онлайн-обучению iSpring Days 2025

Москва • Онлайн

Больше событий в календаре

Администрирование

Менеджмент

Другое

19 сентября

Премия для технологических стартапов Startech.Awards 2025

Москва • Онлайн

Больше событий в календаре

Другое

30 сентября

VII премия в сфере фармацевтического маркетинга и креатива MedMen Awards 2025

Онлайн

Больше событий в календаре

Маркетинг

Другое

30 октября

Премия «Проксима»

Москва

Больше событий в календаре

Маркетинг

Реклама

ООО «Хабр»

ИНН 7705756279

erid: 2VSb5wN9Qsb

IT в ритейле

Свайпни и узнай, твоё ли это

Ваш аккаунт

Профиль

Трекер

Диалоги

Настройки

ППА

Разделы

Статьи

Новости

Хабы

Компании

Авторы

Песочница

Информация

Устройство сайта

Для авторов

Для компаний

Документы

Соглашение

Конфиденциальность

Услуги

Корпоративный блог

Медийная реклама

Нативные проекты

Образовательные программы

Стартапам

Настройка языкаТехническая поддержка
© 2006–2025, Habr